package com.test.demo;

/**
 * Created by jl on 2017/11/15.
 */
public class InsertSort {

    public static void main(String[] args) {
        int[] arr = {4, 3, 1, 2};
        insertSort(arr);
        print(arr);
    }

    private static void print(int[] arr) {
        for (int a : arr) {
            System.out.println(a);
        }
    }

    private static void insertSort(int[] arr) {
        int len = arr.length;
//        int pointer = 0; //已排好序的下界限
        int insPos;
        for(int i = 1; i < len; i++) {
            insPos = findInsPos(arr, i, i - 1);
            if (insPos > -1) {
                move(arr, insPos, i);
            }
        }
    }

    private static void move(int[] arr, int insPos, int i) {
        int tmp = arr[i];
        for (int j = i; j > insPos; j--) {
            arr[j] = arr[j - 1];
        }
        arr[insPos] = tmp;
    }

    private static int findInsPos(int[] arr, int i, int pointer) {
        if (arr[i] <= arr[0]) {
            return 0;
        }
        if (arr[i] >= arr[pointer]) {
            return -1;
        }
        for (int j = 1; j <= pointer - 1; j++) {
            if (arr[i] < arr[j]) {
                return j;
            }
        }
        return -1;
    }
}
